1. Field of the Invention
This invention relates to computer systems. In particular, the invention relates to data representation for media information.
2. Description of Related Art
Progressive mesh (PM) representation is a scheme for representing highly detailed three-dimensional (3-D) graphic models at continuous resolutions. The graphic models are usually tessellated into polygonal approximations, referred to as meshes. In many simplified models, the polygons are triangles.
Progressive meshes are typically based on pair-contraction, vertex decimation, or edge collapse operations. Pair contraction is based on the iterative contraction of vertex pairs. Vertex decimation iteratively selects a vertex for removal, removes all adjacent faces, and retriangulates the resulting hole. Edge collapse unifies two adjacent vertices into a single vertex according to a selected sequence of transformations.
Among these techniques, pair contraction provides several advantages. The primary advantage is the ability to join previously unconnected regions of the model together. The technique is therefore less sensitive to the mesh connectivity of the original model.
However, the implementation of the pair-contraction technique has a number of disadvantages. The technique represents models using an adjacency graph structure: vertices and faces are all explicitly represented and linked together. Edges may also be derived from vertices and faces. The representation typically enumerate surrounding vertices based on position and encode the connectivity in terms of this ordering. The amount of encoded representation is large and therefore results in inefficient compression.
Therefore, there is a need in the technology to provide a simple and efficient method to represent connectivity in progressive meshes.
Briefly, in one embodiment, the present invention is a method for representing a connectivity of an object, having N vertices, in a pair-contracting operation. The method comprises (i) encoding a parent vertex in the N vertices, the parent vertex being used in the pair-contracting operation, and (ii) encoding a symbol of the connectivity related to the parent vertex.